带有推测的动态调度
AP SHANTHI博士
本模块的目标是通过硬件推测的概念，并讨论如何通过推测来增强动态调度。我们将研究数据结构如何维护相关信息以及如何处理危险。
我们首先回顾一下动态调度。动态调度是一种技术，其中硬件重新安排指令执行以减少停顿，同时保持数据流和异常行为。动态调度的优点是：
它处理在编译时依赖项未知的情况
–（例如，因为它们可能涉及内存引用）
它简化了编译器
它允许为一个管道编译的代码在不同的管道上高效运行
硬件推测，一种具有显着性能优势的技术，建立在动态调度之上
在动态调度的流水线中，所有指令按顺序通过发布阶段；然而，它们可以在第二阶段停止或相互绕过，从而进入乱序执行。指令也将无序完成。
我们在前面的模块中讨论的动态调度技术不允许处理器在分支之外执行指令。动态分支预测有利于循环的动态展开。但是，分支后的指令只能取和解码，不能执行。这是因为如果分支预测失败，则没有规定可以撤销指令的影响。但是，这再次限制了可以利用的并行性。因此，如果我们需要发现更多的并行性，我们甚至需要在分支解决之前执行指令。这种在解决分支之前推测执行指令的概念称为硬件推测。在每个周期中，处理器都会执行一条指令——即使它可能是错误的操作说明。这是克服控制依赖的另一种方法——通过推测分支的结果并执行程序，就好像我们的猜测是正确的一样。显然，如果我们的猜测出错，我们应该有撤销的规定。我们本质上是在构建数据流执行模型，以便在操作数可用时立即执行指令。本模块讨论了这种推测性执行的细节。
带有推测的动态调度包含三个组成部分。他们是：
动态分支预测以选择要执行的指令
允许在解决控制依赖之前执行指令的推测
o 支持在预测错误时撤消
动态调度处理基本块不同组合的调度处理器，如 PowerPC 603/604/G3/G4、MIPS R10000/R12000、Intel Pentium II/III/4、i3、i5、i7、Alpha 21264、AMD K5/ K6/Athlon 等使用带有推测的动态调度。
基于硬件的推测：早期的动态调度，分支后的指令只有在分支解决后才执行。因此，在回写阶段，他们写入寄存器或内存。现在，通过推测，我们沿着预测的执行路径执行指令，并且只有在预测正确的情况下才能提交结果。只有当指令不再是推测性的时，指令提交才允许指令更新寄存器文件或存储器。
这表明我们需要一个额外的硬件来缓冲指令的结果，直到它们提交。这块硬件叫做Reorder Buffer，缩写为ROB。这有助于防止任何不可撤销的操作，直到指令提交，即更新状态或执行。重新排序缓冲区保存一条指令从执行到提交的结果。它还用于在推测的指令之间传递操作数。
重新排序缓冲区具有以下字段。他们是：
用于识别的名称或标签字段
指令类型：分支/存储/注册
目标字段：注册号
值字段：输出值
就绪字段：完成执行？
ROB 就像保留站一样扩展架构寄存器。通过对推测的支持，我们现在使用其 ROB 条目而不是保留站条目来识别指令。保留站保存着从指令发出到执行的操作数。ROB 会缓冲从指令执行到它提交的时间的结果。然而，我们正在查看一个有序提交，并在指令本身发出时分配一个 ROB 条目。映射是在寄存器、保留站和 ROB 之间完成的。这有助于避免 WAW 和 WAR 危险。为了处理控制风险，如果发生错误预测，则 ROB 中的推测条目将被清除。请注意，在导致异常的指令准备提交之前，异常不会被识别。
图 19.1 给出了带有推测的动态调度器的整体架构。它与我们在前面的模块中讨论的架构相同，只是增加了一个 ROB。
指令从预取指令队列中取出并解码。解码阶段或发布阶段对指令进行解码并检查结构性危险。保留站或 ROB 条目的不可用会导致结构性危险。保留站条目是根据指令类型分配的，而 ROB 条目是顺序分配的（按顺序发布和按顺序提交）。由于我们正在查看一个有序的问题，如果一条指令在发布阶段停滞，则无法发布后续指令。之后，指令将等待直到没有数据危险，然后再读取操作数。这将使我们能够按顺序发出、乱序执行和乱序完成。计算结果后，结果仅写入适当的 ROB 条目和等待此数据的保留站。请注意，CDB 仅写入 ROB 和保留站，而不写入寄存器文件。另一个变化是我们没有单独的存储缓冲区。ROB 条目本身充当存储缓冲区条目。它们缓冲存储地址和要存储的数据，直到轮到存储指令提交为止。寄存器结果状态指示哪个寄存器将由哪个 ROB 标签写入。在提交阶段，数据从 ROB 传输到寄存器或内存。如果提交的指令是分支，则检查预测，如果预测正确，则从 ROB 队列中删除分支，并按顺序提交后续指令。否则，
整个簿记是在硬件中完成的。硬件考虑一组称为指令窗口的指令，并尝试根据操作数的可用性重新安排这些指令的执行。硬件维护每条指令的状态并决定每条指令何时从一个阶段移动到另一个阶段。寄存器重命名是在保留站和 ROB 的帮助下在硬件中完成的。这消除了 WAW 和 WAR 危险。
除了动态调度器中的三个步骤之外，当支持推测时，还引入了一个额外的提交步骤。下面列出了带有推测的动态调度程序的四个步骤：
问题
从 FIFO 队列中获取下一条指令
如果可用 RS 条目和 ROB 条目，则发出指令
如果 RS 或 ROB 条目不可用，则会成为结构性危险并且指令会停止
如果没有发出较早的指令，则不能发出后续指令
如果操作数可用，则读取它们并将它们存储在保留站中
操作数可以从寄存器文件（已提交的指令）或从 ROB（已执行但尚未提交）中读取
依赖于较早指令的操作数由它们在 Q 字段中的相应 ROB 标记标识，并且此类指令将不得不暂停，直到数据可用
执行
CDB 使用 ROB 标签广播数据，当操作数可用时，将其存储在任何等待它的保留站中
当所有操作数准备好后，发出执行指令
一旦指令进入执行状态，释放保留站入口
通过有效地址按程序顺序维护加载和存储
即使有挂起的分支，指令也会被推测执行
写入结果
将CDB上的结果写入保留站和ROB
犯罪
当一条指令到达 ROB 的头部并且其结果出现在缓冲区中时，就会提交一条指令
如果是 ALU 或 Load 指令，则用结果更新寄存器并将该指令从 ROB 中移除
提交存储是类似的，除了更新内存而不是结果寄存器
如果预测错误的分支到达ROB的头部，则表明推测错误
ROB 被刷新并在分支的正确后继处重新开始执行
如果分支被正确预测，则从 ROB 中删除该分支
一旦一条指令提交，它在 ROB 中的条目就会被回收。
如果 ROB 被填满，我们只是停止发出指令，直到一个条目被释放。
带有推测的动态调度程序维护四种数据结构——保留站、ROB、一个寄存器结果数据结构，用于跟踪将修改寄存器的 ROB 条目和一个指令状态数据结构。最后一个更多是为了理解目的。
在了解了带有推测的动态调度程序的基础知识之后，我们现在将讨论调度是如何针对指令序列发生的。让我们考虑我们之前讨论的动态调度指令序列。假设 Add、Mul 和 Div 指令的延迟分别为 2、6 和 12。
LD F6,32(R2)
LD F2,44(R3)
MUL.D F0,F2,F4
SUB.D F8,F6,F2
DIV.D F10,F0,F6
ADD.D F6,F8,F2
图 19.2 显示了当 MUL.D 准备好提交时状态表的样子。请注意，虽然 Sub 和 Add 指令已写入结果，但它们尚未提交。这是因为 Mul 指令尚未提交。Dest 字段指定 ROB 条目，该条目是特定保留站条目产生的结果的目的地。完整的时间表在表 19.1 中给出。
操作说明 问题在 执行于 将结果写入 提交于
LD F6,32(R2)
1 2-3 4 5
L.DF2,44(R3)
2 3-4 5 6
MUL.D F0,F2,F4
3 6-11 12 13
SUB.D F8,F6,F2
4 6-7 8 14
DIV.D F10,F0,F6
5 13-24 25 26
ADD.D F6,F8,F2
6 9-10 11 27
表 19.1
请注意，指令是按顺序发出的，按顺序执行的，按顺序完成的，但按顺序提交的。
推测执行的一个含义是它维护一个精确的异常模型。例如，如果 MUL.D 指令导致异常，我们会等到它到达 ROB 的头部并处理异常，从 ROB 中清除任何其他挂起的指令。因为指令提交是按顺序发生的，所以这会产生一个精确的异常。相比之下，在使用 Tomasulo 算法的示例中，SUB.D 和 ADD.D 指令都可以在 MUL.D 引发异常之前完成。结果是寄存器 F8 和 F6（SUB.D 和 ADD.D 指令的目标）可能被覆盖，并且异常将是不精确的。因此，除了支持推测执行之外，使用具有有序指令提交的 ROB 还提供了精确的异常。
当我们考虑带有分支的序列时，请记住循环是由动态分支预测器动态展开的，并且分支之后的指令是推测性执行的。但是，在解决分支后，它们会按顺序提交。
观察到存在有序问题、无序执行、无序完成和有序提交。由于重命名过程，多次迭代对寄存器使用不同的物理目的地（动态循环展开）。这就是为什么 Tomasulo 的方法能够重叠循环的多次迭代。保留站允许指令发出提前通过整数控制流操作。它们缓冲寄存器的旧值，从而完全避免否则会发生的 WAR 停顿。因此，我们可以说 Tomasulo 的推测方法动态地构建了数据流执行图。然而，性能提升取决于分支预测的准确性。如果分支预测出错，获取的指令，
实际上，推测的处理器会在分支被错误预测后尽可能早地恢复。这种恢复可以通过清除出现在错误预测分支之后的所有条目的 ROB 来完成，允许 ROB 中的分支之前的条目继续，并在正确的分支后继处重新开始提取。在推测处理器中，性能对分支预测更敏感，因为错误预测的影响会更高。因此，处理分支的所有方面——预测准确性、错误预测检测的延迟和错误预测恢复时间——都变得越来越重要。
就像 Tomasulo 的算法一样，我们必须通过记忆来避免危险。内存中的 WAW 和 WAR 危险通过推测被消除，因为内存的实际更新是按顺序发生的，当一个存储位于 ROB 的头部时，因此，没有更早的加载或存储仍然可以挂起。通过内存的 RAW 危害由两个限制维护：
如果存储占用的任何活动 ROB 条目具有与加载的 A 字段的值匹配的 Destination 字段，则不允许加载启动其执行的第二步，并且
维护程序顺序，以计算与所有较早存储相关的负载的有效地址。
这两个限制一起确保访问由较早存储写入的内存位置的任何负载在存储写入数据之前无法执行内存访问。当这种 RAW 危险发生时，一些推测处理器实际上会直接将值从存储绕过到加载。
总而言之，我们已经研究了硬件推测的概念，它允许在解决分支之前执行分支之外的指令。根据分支预测，动态展开分支。分支之外的指令被提取、发出和执行，但按顺序提交。已经详细说明了簿记完成和执行的各个步骤。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。